1207. sqrt log sin

The evil professor has just given you the following task. Let’s define a sequence as follows:

x₀ = 1,

x_i = + +

For each given value of i, compute x_i.

Input. Consists of multiple lines, each containing one integer i (0 ≤ i ≤ 10⁶). The last line contains -1 and should not be processed.

Output. For each value of i (except the last -1), print the corresponding value of x_i, computed modulo 10⁶.

Sample input	Sample output
0 1 2 10 -1	1 3 5 21

SOLUTION

recurrent relation

Algorithm analysis

The value of x_i will be computed using the function f(i). To do this, we need to implement the recurrence relation:

= + + ,

while storing the values of f(i) in a linear array dp of size 10⁶.

Algorithm implementation

Store the values of x_i in the array dp.

#define MAX 1000001

int dp[MAX];

The function f(n) computes the value of x_n.

int f(int n)

{

Terminate the recursion when n = 0.

if (n == 0) return 1;

If the value of x_n is already computed (dp[n] ≠ -1), return it.

if (dp[n] != -1) return dp[n];

Recursively compute the first, second, and third terms.

int a = f((int)(n - sqrt(n)));

int b = f((int)(log(n)));

int c = f((int)(n * sin(n) * sin(n)));

Compute, store, and return the value of x_n.

return dp[n] = (a + b + c) % 1000000;

}

The main part of the program. Let dp[i] = -1 if the value of x_i is not computed yet.

memset(dp,-1,sizeof(dp));

Process multiple test cases. For each value of n, print the result.

while(scanf("%d",&n), n != -1)

printf("%d\n",f(n));

Algorithm implementation – nonrecursive

Store the values of x_i in the array x.

int x[1000001];

Fill the elements of the array x according to the given recurrence relation.

x[0] = 1;

for (i = 1; i <= 1000000; i++)

x[i] = (x[(int)(i - sqrt(i))] + x[(int)(log(i))] +

x[(int)(i * sin(i) * sin(i))]) % 1000000;

Process multiple test cases. For each value of n, print the result.

while (scanf("%d", &n), n != -1)

printf("%d\n", x[n]);

Java implementation

import java.util.*;

public class Main

{

static int dp[] = new int[1000001];

static int f(int n)

{

if (n == 0) return 1;

if (dp[n] != -1) return dp[n];

int a = f((int)(n - Math.sqrt(n)));

int b = f((int)(Math.log(n)));

int c = f((int)(n * Math.sin(n) * Math.sin(n)));

return dp[n] = (a + b + c) % 1000000;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

Arrays.fill(dp, -1);

while(true)

{

int n = con.nextInt();

if (n == -1) break;

System.out.println(f(n));

}

con.close();

}

}

Python implementation

import math

Initialize the array x.

x = [0] * 1000001

x[0] = 1

Fill the elements of the array x according to the given recurrence relation.

for i in range(1, 1000001):

x[i] = (x[int(i - math.sqrt(i))] +

x[int(math.log(i))] +

x[int(i * math.sin(i)**2)]) % 1000000

Process multiple test cases. For each value of n, print the result.

while True:

n = int(input())

if n == -1:

break

print(x[n])